\documentclass[a4paper,12pt]{article}

\usepackage[T2A]{fontenc} 
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{listings}
\usepackage[dvips]{graphicx}
\usepackage{indentfirst}
\usepackage{color}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{geometry}
\geometry{left=1.5cm}
\geometry{right=1.5cm}
\geometry{top=1cm}
\geometry{bottom=2cm}

\graphicspath{{images/}}

\begin{document}
\sloppy

\lstset{
	basicstyle=\small,
	stringstyle=\ttfamily,
	showstringspaces=false,
	columns=fixed,
	breaklines=true,
	numbers=right,
	numberstyle=\tiny
}

\newtheorem{Def}{Определение}[section]
\newtheorem{Th}{Теорема}
\newtheorem{Lem}[Th]{Лемма}
\newenvironment{Proof}
	{\par\noindent{\bf Доказательство.}}
	{\hfill$\scriptstyle\blacksquare$}
\newenvironment{Solution}
	{\par\noindent{\bf Решение.}}
	{\hfill$\scriptstyle\blacksquare$}


\begin{flushright}
	Кринкин М. Ю. группа 504 (SE)
\end{flushright}

\section{Домашнее задание 3}

\paragraph{Задача 1.} Найти число разбиений числа $k$ на $n$ слагаемых при следующих ограничениях:
\begin{enumerate}
\item $a_1+a_2+...+a_n=k$, $a_i \le s_i \le 0$, $s=s_1+s_2+...+s_n \le k$

\item $a_1+a_2+...+a_n=k$, $0 \le a_i \le m_i$, $m=m_1+m_2+...+m_n \ge k$
\end{enumerate}

\begin{Solution}
\begin{enumerate}
\item Задача разложения числа на фиксированное число слагаемых эквивалентна распределению $k$ единиц по $n$ позициям, т. е. $\left(\binom{n}{k}\right)$, в случае ограничений снизу на значение переменной можно считать, что $s$ единиц уже распределены, а следовательно решение задачи $\left(\binom{n}{k-s}\right)$

\item В случае ограничений снизу все сложнее. Первое решение заключается в том, чтобы посмотреть на динамику изменений и выввести формулу. Пусть $m = k$, в этом случае количесто решений равно 1, пусть теперь $m = k+1$, в данном случае на всех переменных кроме одной выполняется условие $a_i=m_i$, а на одной из них $a_j+1 = m_j$. Далее рассматриваем $m=k+2$,  этом случае выбираем уже $2$ позиции из $n$ с поторениями, не трудно увидеть, что если в прошлом случае мы распределяли единицы, то в данном наоборот распределяем <<дыры>>, получаем решение $\left(\binom{n}{m-k}\right)$.
\end{enumerate}
\end{Solution}

\paragraph{Задача 2.} Имеется 32 шара четырех различных цветов, по 8 шаров каждого цвета. Найти количество различных наборо, содержащих:
\begin{enumerate}
\item ровно 5 шаров;

\item не более 5 шаров?
\end{enumerate}

\begin{Solution}
\begin{enumerate}
\item Если учитывается порядок следования шаров различных типов в выборке, то решением будет число различных отображений из множества мощностью $5$ в множество мощностью $4$ (т. е. сопоставления позиций видам шаров) и равно $4^5$. Если порядок следования элементов не важен, а важно лишь количество элементов каждого класса $\left(\binom{4}{5}\right)$

\item Для не более 5 шаров, без учета порядка, очевидно, будет сумма $\sum_{i=0}^{5} \left(\binom{4}{i}\right)$, аналогично с учетом порядка $\sum_{i=0}^{5}4^i$
\end{enumerate}
\end{Solution}

\paragraph{Задача 3.} На складе имеется $n$ различных видов товаров, упакованных в коробки одинакового размера, на которых написано, какой вид товара в них упакован. Коробки, содержащие товар одного вида, склеены скотчем в блоки, содержащие как минимум по $s$ коробок в каждом. Сосчитать количество способов загрузки грузовика, в кузове которого может поместиться не более чем $k$ коробок, при условии, что в грузовик должен быть загружен товар каждого вида.

\begin{Solution}
Задача эквивалентна разбиению числа $k$ на $n$ слогаемых, при этом каждое слогаемое должно быть не меньше $s$, т. е. необходимо разложить $k-sn$ на $n$ слогаемых: $\left(\binom{n}{k-sn}\right)$, при условии, что порядок расположения в грузовике не важен.
\end{Solution}

\paragraph{Задача 4.} Найти число $C_1 \left(n,k\right)$ таких $k$-сочетаний без повторений из множества $X = \{1,2,...,n\}$ первых $n$ натуральных чисел, которые не содержат пары последовательно идущих чисел. Сосчитать общее число $C_n$ всех таких подмножеств $n$-множества $X$. Вывести рекуррентное соотношение для чисел $C_n$. Что это за числа?

\begin{Solution}
Закодирем каждое подмножество двоичным числом, в котором 1 соответсует, что элемент входит в сочетание, а 0 - что не входит. Требуется посчитать все такие двоичные числа, в которых единицы не идут последовательно. Получть такие числа можно из следующих соображений, расставим в ряд $n-k$ нулей с промежутками, с учетом места перед нулями, после и между ними имеется $n-k+1$ позиций, на которые можно поставить единицы, таким образом решение $\binom{n-k+1}{k}$. Число всех таких подмножеств получается суммированием по $k$, т. е. $\sum_{i=0}^{n/2}\binom{n-i+1}{i} = \sum_{i=0}^n \binom{n-i+1}{i}$

Для вывода рекуррентного соотношения зафиксируем число $n$, посчитаем все возможные подмножества, не содержащие последовательных пар чисел, для множества из $n-1$ элемента, таких по определению $C_{n-1}$. Среди этих подмножеств нет содержащих элемент $n$ (по построению), рассмотрим к каким из них мы можем добавить элемент $n$ и получить правильное подмножество. Это все правильные подмножества чисел множества из $n-2$ элемента (т. е. все те, которые не содержат элемент $n-1$), а таких $C_{n-2}$, кроме того сам элемент $n$ является удовлетворяющей последовательностью, вместе $C_n = C_{n-1}+C_{n-2}+1$. Начальные условия: $C_1 = 1, C_2 = 2$, получили последовательность чисел Фибоначчи минус 1 (со сдвигом).
\end{Solution}

\paragraph{Задача 5.} Пусть $f=\left(f_0,f_1,f_2,...\right)$, $g=\left(g_0,g_1,g_2,...\right)$ - две числовые последовательности, связанные соотношением
\[
	f_k = \sum_{i=0}^k \binom{k}{i} g_i
\]
Доказать, что тогда
\[
	g_k = \sum_{i=0}^k {\left(-1\right)}^{k-i}\binom{k}{i} f_i
\]
Показать, что это эквивалентно следующим формулам обращения:
\[
	f_k = \sum_{i=0}^k {\left(-1\right)}^{k-i} \binom{k}{i}f_i \Leftrightarrow g_k = \sum_{i=0}^k {\left(-1\right)}^i \binom{k}{i}f_i
\]

\begin{Solution}
\[
	\begin{split}
		& f_k = \sum_{i=0}^k \binom{k}{i}g_i = g_k + \sum_{i=0}^{k-1} \binom{k}{i}g_i \Leftrightarrow g_k = f_k - \sum_{i=0}^{k-1}g_i = \\
		& = f_k - \sum_{i=0}^{k-1} \binom{k}{i} \left[\sum_{l=0}^i {\left(-1\right)}^{i-l} \binom{i}{l} f_l \right] = f_k - \sum_{i=0}^{k-1}\sum_{l=0}^i {\left(-1\right)}^{i-l} \binom{k}{i}\binom{i}{l} = \\
		& = f_k - \sum_{l=0}^{k-1}f_l \left[\sum_{i=l}^{k-1} {\left(-1\right)}^{i-l} \binom{k}{i} \binom{i}{l}\right]
	\end{split}
\]
рассмотрим внутреннюю сумму отдельно:
\[
	\begin{split}
		& \sum_{i=l}^{k-1} {\left(-1\right)}^{i-l} \binom{k}{i} \binom{i}{l} = \sum_{i=l}^{k-1} {\left(-1\right)}^{i-l} \frac{k!}{\left(k-i\right)!\left(i-l\right)!l!} = \\
		& = \frac{k!}{\left(k-l\right)!l!} \sum_{i=0}^{k-1-l} {\left(-1\right)}^{i} \binom{k-l}{i} = \binom{k}{l}\sum_{i=0}^{k-1-l} {\left(-1\right)}^i \binom{k-l}{i} \pm \binom{k}{l}{\left(-1\right)}^{k-l} \binom{k-l}{k-l} = \\
		& = -\binom{k}{l}{\left(-1\right)}^{k-l}
	\end{split}
\]
полученный результат вставляем в исходную формулу:
\[
	\begin{split}
		& f_k - \sum_{l=0}^{k-1}f_l \left[\sum_{i=l}^{k-1} {\left(-1\right)}^{i-l} \binom{k}{i} \binom{i}{l} \right] = f_k + \sum_{l=0}^{k-1} \binom{k}{l} {\left(-1\right)}^{k-l} f_l = \sum_{l=0}^{k} {\left(-1\right)}^{k-l} \binom{k}{l} f_l
	\end{split}
\]

Во время доказательства использовалось утерждение, что $g_l = \sum_{i=0}^k {\left(-1\right)}^{k-i} \binom{k}{i} f_i$ для $l<k$, т.е. для полного доказательства необходимо проверить базу индукции, я ее проверил.

Проверим теперь, что из первой пары формул обращения следует вторая:
\[
\begin{split}
	& f_k = \sum_{i=0}^{k} {\left(-1\right)}^{i} \binom{k}{i} g_i \Leftrightarrow f_k {\left(-1\right)}^{k} = \sum_{i=0}^{k} {\left(-1\right)}^{i+k} \binom{k}{i} g_i = \sum_{i=0}^{k} {\left(-1\right)}^{k-i} \binom{k}{i} g_i \Leftrightarrow \\
	& \Leftrightarrow g_k = \sum_{i=0}^k \binom{k}{i} \left[{\left(-1\right)}^{-i} f_k\right] = \sum_{i=0}^{k} {\left(-1\right)}^{i} \binom{k}{i}
\end{split}
\]
\end{Solution}

\paragraph{Задача 6.}

\paragraph{Задача 7.} Сосчитать количество размещений $n$ различимых предметов по $k$ различимым ящикам при условии, что только $r$ из $k$ могут быть заняты.

\begin{Solution}
Выберем $r$ ящиков из $k$, число способо сделать это $\binom{k}{r}$. Зафиксируем вектор из $r$ натуральных чисел, сумма которых равна $n$, каждое число обозначает количество предметов в соотетствующем ящике, количество способов получается
\[
	\begin{split}
		& \frac{n!}{a_1!a_2!...a_r!} \\
		& a_1+a_2+...+a_r=n
	\end{split}
\]
Число способов разместить $n$ предметов ровно по $r$ ящикам тогда получается равным:
\[
	\binom{k}{r}\sum_{\substack{a_1,a_2,...,a_r>0 \\ a_1+a_2+...+a_r=n}} \frac{n!}{a_1!a_2!...a_r!} = \binom{k}{r} \hat S \left(n,r\right)
\]
Если может быть занято не более $r$, тогда общее количество:
\[
	\sum_{i=1}^{r} \binom{k}{i} \hat S \left(n,i\right)
\]
\end{Solution}

\paragraph{Задача 8.} В начале учебного года на кафедре происходит распределение нагрузки. Имеется 5 преподавателей и 7 различных групп студентов. Любой преподаватель может вести занятия в любой группе. Подсчитать количество способов распределения нагрузки между преподавателями при условии, что каждый преподаватель должен вести занятия хотябы в одной группе.

\begin{Solution}
Сначала разделим 7 на 5 натуральных слагаемых, сделать это можно только двумя существенно различными способами $7=2+2+1+1+1=3+1+1+1+1$.

Рассмотрим первое распределение. Распределить группы по этим преподавателям, так чтобы удовлетворить спецификации можно $\frac{7!}{3!}$ способами. Количество способов выбора преподавтеля читающего 3 лекции осуществляется 5 способами.

Рассмотрим торое распределение. Распределить группы между преподавателями, так чтобы удовлетворить спецификации можно $\frac{7!}{2!2!}$. Количество способов выбрать дух преподавателей ведущих по 2 группы равно $\binom{5}{2} = 10$

Результат:
\[
	5 \cdot \frac{7!}{3!} + 10 \cdot \frac{7!}{2!2!} = 16800
\] 
\end{Solution}

\end{document}
